알고리즘 풀이 - 삼각 달팽이

picture 22

삼각 달팽이

문제 링크

문제 요약

제한사항

  • n은 1 이상 1,000 이하입니다.

Input

  • 정수 n(삼각형의 높이)

output

  • 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열

해결방법

  • up, down, fill의 세가지 상태로 나누어 상태에 따라 처리
  • 삼각형을 우선 만들고 배열을 합쳐서 리턴
function solution(n) {
  const triangle = []
  const meta = []
  let totalCount = 0
  for (let i = 0; i < n; i++) {
    triangle.push(new Array(i + 1))
    meta.push({ start: 0, end: i })
    totalCount += i + 1
  }
  let mode = 'DOWN'
  let line = 0
  for (let i = 1; i <= totalCount; i++) {
    if (mode === 'DOWN') {
      triangle[line][meta[line].start] = i
      meta[line].start++
      line++
      const nextLine = meta[line + 1]
      if (nextLine === undefined || nextLine.end < nextLine.start) {
        mode = 'FILL'
      }
    } else if (mode === 'FILL') {
      triangle[line][meta[line].start] = i
      meta[line].start++
      if (meta[line].start > meta[line].end) {
        mode = 'UP'
        line--
      }
    } else if (mode === 'UP') {
      triangle[line][meta[line].end] = i
      meta[line].end--
      line--
      const nextLine = meta[line]
      if (nextLine === undefined || nextLine.end < nextLine.start) {
        mode = 'DOWN'
        line += 2
      }
    }
  }
  const result = triangle.reduce((prev, curr) => prev.concat(curr))
  return result
}

개선사항

다른 사람의 모범 풀이

소스 내부 동작을 직관적으로 이해하기는 힘들지만 소스가 간결하고 예쁘다.

해당 소스를 보면서 내 소스의 변수명도 변경해야겠다는 생각이 든다.

array.flat() 함수의 존재를 알았다.

function solution(n) {
  let a = Array(n)
    .fill()
    .map((_, i) => Array(i + 1).fill())
  let row = -1
  let col = 0
  let fill = 0
  for (let i = n; i > 0; i -= 3) {
    a[++row][col] = ++fill
    for (let j = 0; j < i - 1; j++) a[++row][col] = ++fill
    for (let j = 0; j < i - 1; j++) a[row][++col] = ++fill
    for (let j = 0; j < i - 2; j++) a[--row][--col] = ++fill
  }
  return a.flat()
}

리팩토링

function solution(n) {
  const result = []
  const meta = []
  let totalCount = 0
  for (let i = 0; i < n; i++) {
    result.push(new Array(i + 1))
    meta.push({ start: 0, end: i })
    totalCount += i + 1
  }
  let mode = 'DOWN'
  let row = 0
  for (let i = 1; i <= totalCount; i++) {
    if (mode === 'DOWN') {
      result[row][meta[row].start] = i
      meta[row].start++
      row++
      const nextLine = meta[row + 1]
      if (nextLine === undefined || nextLine.end < nextLine.start) {
        mode = 'FILL'
      }
    } else if (mode === 'FILL') {
      result[row][meta[row].start] = i
      meta[row].start++
      if (meta[row].start > meta[row].end) {
        mode = 'UP'
        row--
      }
    } else if (mode === 'UP') {
      result[row][meta[row].end] = i
      meta[row].end--
      row--
      const nextLine = meta[row]
      if (nextLine === undefined || nextLine.end < nextLine.start) {
        mode = 'DOWN'
        row += 2
      }
    }
  }
  return result.flat()
}

Written by@박대성

독서와 지식관리에 관심이 많은 개발자

GitHub